/* 两个递增有序表，求它们合并后的第k小数 */

#include <iostream>
#include "sqlist.cpp"
using namespace std;

int find_k(Sqlist &A, Sqlist &B, int k)
{
	// 不妨令 A.length <= B.length
	if (A.length > B.length)
		return find_k(B, A, k);
	
	// 查找范围
	int a0 = 0, b0 = 0;
	
	while (true)
	{
		// 如果A顺序表查找完毕
		if (a0 == A.length) return B.data[b0 + k - 1];
		
		// 如果查找的是最小值
		if (k == 1) return min(A.data[a0], B.data[b0]);
		
		// 如果k不符合要求
		if (k < 1) return -999;
		
		// 其他情况
		int a_id = min(A.length, a0 + k / 2);
		int b_id = b0 + k - k / 2;
		
		// 更新查找范围与查找目标
		if (A.data[a_id-1] < B.data[b_id-1])
		{
			k -= a_id - a0;
			a0 = a_id;
		}
		else 
		{
			k -= b_id - b0;
			b0 = b_id;
		}
	}
}

int main(int argc, char *argv[]) {
	// 创建两个递增有序表
	Sqlist A = {{11, 12, 13, 14, 15, 17, 19, 20}, 8};
	Sqlist B = {{2, 4, 6, 8, 20}, 5};
	
	// 找到两个表的中位数
	cout << find_k(A, B, 8) << endl;
}